#include "./basic-sort.h"

void bubbleSort(SqList &list)
{
	for (int i = 0; i < list.length - 1; i++)
	{
		for (int j = 0; j < list.length - i - 1; j++)
		{
			if (list.elem[j] > list.elem[j + 1])
			{
				swap(list, j, j + 1);
			}
		}
	}
}

void selectSort(SqList &list)
{
	int min;
	for (int i = 0; i < list.length; i++)
	{
		min = i; // 先定义当前的元素下标是最小值元素
		// 找到i之后最小的一个元素，并交换当前元素和最小元素
		for (int j = i; j < list.length; j++)
		{
			if (list.elem[j] < list.elem[min])
			{
				min = j;
			}
		}
		if (i != min)
		{
			swap(list, i, min);
		}
	}
}

void insertSort(SqList &list)
{
	int tmp, j; // 作为监视哨临时变量，用于拿出并插入
	// 插入排序，从第二个开始，判断第i个元素（当前元素）是否小于第i - 1个元素
	for (int i = 1; i < list.length; i++)
	{
		if (list.elem[i] < list.elem[i - 1])
		{
			tmp = list.elem[i];
			// 记录往后移
			for (j = i - 1; list.elem[j] > tmp; j--)
			{
				list.elem[j + 1] = list.elem[j];
			}
			// 插入到正确位置
			list.elem[j + 1] = tmp;
		}
	}
}